package Algorithm.DynamicPlanning;

public class Code11_PalindromeWays {

    // 四种情况：dp[L,R]代表L到R的回文串个数
    // 1. 既不以L开头，也不以R结尾 dp[L+1][R-1]
    // 2. 不以L开头，以R结尾 dp[L+1][R]
    // 3. 以L开头，不以R结尾 dp[L][R-1]
    // 4. 以L开头，以R结尾 dp[L][R]
    public static int way1(String str){
        char[] chas = str.toCharArray();
        int len = chas.length;
        int[][] dp = new int[len + 1][len + 1];
        // 单个字符都是回文串
        for (int i = 0; i <= len; i++) {
            dp[i][i] = 1;
        }
        // 添加普遍情况（斜着填）
        for (int hi = 1; hi < len; hi++){
            for (int i = 1; i <= len - hi; i++){
                int j = i + hi;
                // dp[i + 1][j] = ;// 1,2情况
                // dp[i][j - 1] = ; // 1,3情况
                // 和-1情况,是123情况
                // dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                // 4情况
                /**
                if (chas[i] == chas[j]){
                    dp[i][j] = dp[i + 1][j - 1] + 1;
                }
                 **/
                if (chas[i - 1] != chas[j - 1]){ // 123情况
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                } else { // 1234情况
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1;
                }
            }
        }
        return dp[1][len];
    }

    public static void main(String[] args) {
        System.out.println(way1("ABA"));
        System.out.println(way1("XX"));
    }
}
